package 困难.树;

/**
 * 给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。
 * 漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/count-pairs-with-xor-in-a-range
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 统计异或值在范围内的数对有多少_1803 {

    public static void main(String[] args) {

        System.out.println(Math.pow(2, 15) > 2 * 10000);

        System.out.println(new 统计异或值在范围内的数对有多少_1803().countPairs(
                new int[]{
                        1, 4, 2, 7
                }, 2, 6
        ));

    }

    /**
     * 1，query(x) 表示 <= x 的漂亮对数数目和，题目转换为
     * query(high) - query(low-1)
     * 2，使用字典树存一个数的二进制位，根节点存高位
     * 3，如何判断 nums[j] 和 nums[0,j-1] (nums[i]) 的数对是否 <= x
     * 遍历到 nums[j] 时，所有 nums[i] 已经存储到字典树，从高位开始比较，
     * 分类讨论：
     * 如果 x 的bit位是 0 ，nums[j] 异或 nums[i] 是 1，> x
     * 否则比较下一个bit位
     * 如果 x 的bit位是 1 ，nums[j] ^ nums[i] 是 0 ，< x
     * 否则比较下一个bit位
     * 比较到了最后一位，= x
     */
    public int countPairs(int[] nums, int low, int high) {
        int sum = 0;
        Trie trie = new Trie();

        for (int num : nums) {
            sum += trie.query(num, high) - trie.query(num, low - 1);
            trie.add(num);
        }

        return sum;
    }

    static class Trie {

        // 代表经过此节点的数字个数
        private int count;

        private Trie[] children = new Trie[2];

        public Trie() {
        }

        public void add(int x) {
            Trie trie = this;
            for (int i = 14; i >= 0; i--) {
                int bit = (x >> i) & 1;
                if (trie.children[bit] == null) {
                    trie.children[bit] = new Trie();
                }

                trie.children[bit].count++;
                trie = trie.children[bit];
            }
        }

        // 查询树中所有数字与 numJ 进行异或 <= x 的个数
        public int query(int numJ, int x) {
            Trie trie = this;
            int sum = 0;
            for (int i = 14; i >= 0; i--) {
                int b = (numJ >> i) & 1;
                if (((x >> i) & 1) == 1) {   // x 是 1
                    // 和 numJ 相同位置 ^= 0 说明小于 x ,累加
                    if (trie.children[b] != null) {
                        sum += trie.children[b].count;
                    }
                    // 和 numJ 相反的位置^ = 1
                    if (trie.children[b ^ 1] == null) {
                        return sum;
                    }
                    trie = trie.children[b ^ 1];
                } else {
                    // x 是0，树中和 numJ 相同的位置才有可能 <= x
                    if (trie.children[b] == null) {
                        return sum;
                    }
                    trie = trie.children[b];
                }
            }
            sum += trie.count;
            return sum;
        }
    }

}
